﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using QuickGraph.Algorithms.ShortestPath;

namespace ComplexNetGeneratorLib
{
    public class ComplexNetGenerator
    {
        public ComplexNet generateSmallWorld_Old(int N, int r, double p)
        {
            //Tworzenie N wezlow
            ComplexNet net = new ComplexNet();
            for (int i = 0; i < N; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            //Tworzenie sieci regularnej
            for (int i = 0; i < N; i++)
            {
                for (int j = 1; j <= r; j++)
                {
                    ComplexNetEdge edge = new ComplexNetEdge();
                    edge.id = "edge" + i + j;
                    edge.directed = false;
                    edge.source = net.nodes[i];
                    edge.target = net.nodes[(i + j)%N];
                    net.nodes[i].edges.Add(edge);
                    net.nodes[(i + j) % N].edges.Add(edge);
                    net.edges.Add(edge);
                }
            }

            Random random = new Random();
            for (int i = 0; i < N; i++) //i - nr wezla referencyjnego
            {
                for (int j = 0; j < net.nodes[i].edges.Count; j++) //przegladamy wszystkie jego krawedzie z sasiadami
                {
                    if (random.NextDouble() <= p)//przepinamy krawedz?
                    {
                        ComplexNetNode newTarget = net.nodes[random.Next(N)]; //losowy wezel docelowy
                        if (!net.nodes[i].id.Equals(newTarget.id)) //jesli nie jest tym samym wezlem
                        {
                            if (!nodesConnected(net.edges, net.nodes[i], newTarget)) //jesli wezly nie sa polaczone
                            {
                                net.nodes[i].edges[j].target = newTarget; //polacz
                            }
                        }
                    }
                }
            }

            return net;
        }
       
        public ComplexNet generateSmallWorld(int N, int r, double p)
        {
            //Tworzenie N wezlow
            ComplexNet net = new ComplexNet();
            for (int i = 0; i < N; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            //Tworzenie sieci regularnej
            for (int i = 0; i < N; i++)
            {
                for (int j = 1; j <= r; j++)
                {
                    ComplexNetEdge edge = new ComplexNetEdge();
                    edge.id = "edge" + i + j;
                    edge.directed = false;
                    edge.source = net.nodes[i];
                    edge.target = net.nodes[(i + j) % N];
                    net.nodes[i].edges.Add(edge);
                    net.nodes[(i + j) % N].edges.Add(edge);
                    net.edges.Add(edge);
                }
            }

            Random random = new Random();

            for (int i = 0; i < N; i++) //i - nr wezla referencyjnego
            {
                for (int j = 0; j < net.nodes[i].edges.Count; j++) //przegladamy wszystkie jego krawedzie z sasiadami
                {
                    if (random.NextDouble() <= p)//przepinamy krawedz?
                    {
                        ComplexNetNode newTarget = net.nodes[random.Next(N)]; //losowy wezel docelowy
                        if (!net.nodes[i].id.Equals(newTarget.id)) //jesli nie jest tym samym wezlem
                        {
                            if (!nodesConnected(net.edges, net.nodes[i], newTarget)) //jesli wezly nie sa polaczone
                            {
                                ComplexNetEdge edge = net.nodes[i].edges[j];

                                //usunac z pierwotnego wezla ta krawedz
                                edge.target.edges.Remove(edge);

                                //dodac do nowego wezla ta krawedz
                                newTarget.edges.Add(edge);

                                //polaczyc wezly
                                net.nodes[i].edges[j].target = newTarget; 
                            }
                        }
                    }
                }
            }

            return net;
        }

        private bool nodesConnected(List<ComplexNetEdge> edges, ComplexNetNode node1, ComplexNetNode node2)
        {
            foreach (ComplexNetEdge edge in edges)
            {
                if ((edge.source.id.Equals(node1.id) && edge.target.id.Equals(node2.id)) || (edge.source.id.Equals(node2.id) && edge.target.id.Equals(node1.id)))
                {
                    return true;
                }
            }
            return false;
        }

        public ComplexNet generateScaleFree(int N, int m0, int M)
        {
            ComplexNet net = new ComplexNet();

            //tworzenie m0 wezlow
            for (int i = 0; i < m0; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            //łączenie wierzcholkow kazdy z kazdym
            for (int i = 0; i < m0; i++)
            {
                for (int j = i+1; j < m0; j++)
                {
                    ComplexNetEdge edge = new ComplexNetEdge();
                    edge.id = "edge" + i + j;
                    edge.directed = false;
                    edge.source = net.nodes[i];
                    edge.target = net.nodes[j];
                    net.nodes[i].edges.Add(edge);
                    net.nodes[j].edges.Add(edge);
                    net.edges.Add(edge);    
                }
            }

            Random random = new Random();
            for (int i = m0; i < N; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;

                int sum = 0; //suma stopni wszystkich wezlow sieci (liczba krawedzi + 1)
                int m = 0;
                double r, p = 0;
                r = random.NextDouble();
                for (int j = 0; j < net.nodes.Count; j++)
                {
                    sum += net.nodes[j].edges.Count+1;
                }

                for (int j = 0; j < net.nodes.Count; j++)
                {
                    if (m == M) break;
                    p += (double)(net.nodes[j].edges.Count + 1) / sum;
                    if (r <= p || j == net.nodes.Count-1)
                    {
                        ComplexNetEdge edge = new ComplexNetEdge();
                        edge.id = "edge" + i + j;
                        edge.directed = false;
                        edge.source = node;
                        edge.target = net.nodes[j];
                        node.edges.Add(edge);
                        net.nodes[j].edges.Add(edge);
                        net.edges.Add(edge);
                        m++;
                    }
                }
                net.nodes.Add(node);
            }
            return net;
        }

        public ComplexNet generateScaleFreeSimplified(int N)
        {
            ComplexNet net = new ComplexNet();

            //tworzenie wezla (m0 = 1) poczatkowego
            ComplexNetNode node = new ComplexNetNode();
            node.id = "node0";
            net.nodes.Add(node);

            Random random = new Random();
            for (int i = 1; i < N; i++)
            {
                node = new ComplexNetNode(); //dodajemy nowy węzeł  
                node.id = "node" + i;

                int sum = 0; //suma stopni wszystkich wezlow sieci (liczba krawedzi + 1)
                int m = 0;
                double r, p = 0;
                r = random.NextDouble();
                for (int j = 0; j < net.nodes.Count; j++)
                {
                    sum += net.nodes[j].edges.Count+1;
                }

                // M = 1
                int k = random.Next(net.nodes.Count);
                p += (double)(net.nodes[k].edges.Count + 1) / sum;
                if (r <= p || k == net.nodes.Count-1)
                {
                        ComplexNetEdge edge = new ComplexNetEdge();
                        edge.id = "edge" + i + k;
                        edge.directed = false;
                        edge.source = node;
                        edge.target = net.nodes[k];
                        node.edges.Add(edge);
                        net.nodes[k].edges.Add(edge);
                        net.edges.Add(edge);
                }
                net.nodes.Add(node);
            }
            return net;
        }

        public ComplexNet generateGraphP(int n, double p)
        {
            ComplexNet net = new ComplexNet();

            //tworzenie n wezlow
            for (int i = 0; i < n; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            Random random = new Random();
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (random.NextDouble() <= p)
                    {
                        //tworzenie krawedzi
                        ComplexNetEdge edge = new ComplexNetEdge();
                        edge.id = "edge" + i + j;
                        edge.directed = false;
                        edge.source = net.nodes[i];
                        edge.target = net.nodes[j];
                        net.nodes[i].edges.Add(edge);
                        net.nodes[j].edges.Add(edge);
                        net.edges.Add(edge);
                    }
                }
            }
            return net;
        }

        public ComplexNet generateGraphK(int n, int k)
        {
            ComplexNet net = new ComplexNet();

            //tworzenie n wezlow
            for (int i = 0; i < n; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            List<ComplexNetEdge> edgeList = new List<ComplexNetEdge>();

            //tworzenie krawedzi
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    ComplexNetEdge edge = new ComplexNetEdge();
                    edge.id = "edge" + i + j;
                    edge.directed = false;
                    edge.source = net.nodes[i];
                    edge.target = net.nodes[j];
                    edgeList.Add(edge);
                }
            }
            //losowanie k krawedzi
            Random random = new Random();
            for (int i = 0; i < k; i++)
            {
                int w = random.Next(edgeList.Count - 1);
                edgeList[w].source.edges.Add(edgeList[w]);
                edgeList[w].target.edges.Add(edgeList[w]);
                net.edges.Add(edgeList[w]);
                edgeList.Remove(edgeList[w]);
            }
            return net;
        }

        public ComplexNet generateBAModel(int N, int m0, int M, double p, double q)
        {
            ComplexNet net = new ComplexNet();

            //tworzenie m0 wezlow
            for (int i = 0; i < m0; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            //łączenie wierzcholkow kazdy z kazdym
            for (int i = 0; i < m0; i++)
            {
                for (int j = i + 1; j < m0; j++)
                {
                    ComplexNetEdge edge = new ComplexNetEdge();
                    edge.id = "edge" + i + j;
                    edge.directed = false;
                    edge.source = net.nodes[i];
                    edge.target = net.nodes[j];
                    net.nodes[i].edges.Add(edge);
                    net.nodes[j].edges.Add(edge);
                    net.edges.Add(edge);
                }
            }

            Random random = new Random();

            for (int i = m0; i < N; i++)
            {
                double r = random.NextDouble();
                if (r <= p)
                {
                    //add new link
                    int sIndex = random.Next(net.nodes.Count);
                    double rd = random.NextDouble();
                    double pki = 0;
                    for (int j = 0; j < net.nodes.Count; j++)
                    {
                        double sumKl = 0;
                        for (int l = 0; l < net.nodes.Count; l++)
                        {
                            sumKl += net.nodes[l].edges.Count + 1;
                        }
                        pki += (net.nodes[j].edges.Count + 1) / sumKl;
                        if (rd <= pki && !nodesConnected(net.edges, net.nodes[sIndex], net.nodes[j]) && sIndex != j)
                        {
                            ComplexNetEdge edge = new ComplexNetEdge();
                            edge.id = "edge" + i + "-" + j;
                            edge.directed = false;
                            edge.source = net.nodes[sIndex];
                            edge.target = net.nodes[j];
                            net.nodes[sIndex].edges.Add(edge);
                            net.nodes[j].edges.Add(edge);
                            net.edges.Add(edge);
                            break;
                        }
                    }

                }
                else if (r <= p + q)
                {
                    //rewire link
                    int sIndex = random.Next(net.nodes.Count);
                    int linkIndex = random.Next(net.nodes[sIndex].edges.Count);
                    if (net.nodes[sIndex].edges.Count == 0) continue;
                    ComplexNetEdge edge = net.nodes[sIndex].edges[linkIndex];
                    net.nodes[sIndex].edges[linkIndex].target.edges.Remove(net.nodes[sIndex].edges[linkIndex]);

                    double rd = random.NextDouble();
                    double pki = 0;
                    for (int j = 0; j < net.nodes.Count; j++)
                    {
                        double sumKl = 0;
                        for (int l = 0; l < net.nodes.Count; l++)
                        {
                            sumKl += net.nodes[l].edges.Count + 1;
                        }
                        pki += (net.nodes[j].edges.Count + 1) / sumKl;
                        if (rd <= pki && !nodesConnected(net.edges, net.nodes[sIndex], net.nodes[j]) && sIndex != j)
                        {
                            edge.id = "edge" + i + "-" + j;
                            edge.directed = false;
                            edge.target = net.nodes[j];
                            net.nodes[j].edges.Add(edge);
                            break;
                        }
                    }
                }
                else
                {
                    //new node
                    ComplexNetNode node = new ComplexNetNode();
                    node.id = "node" + i;
                    net.nodes.Add(node);

                    for (int j = 0; j < M; j++)
                    {
                        double rd = random.NextDouble();
                        double pki = 0;
                        for (int k = 0; k < net.nodes.Count; k++)
                        {
                            double sumKl = 0;
                            for (int l = 0; l < net.nodes.Count; l++)
                            {
                                sumKl += net.nodes[l].edges.Count + 1;
                            }

                            pki += (net.nodes[j].edges.Count + 1) / sumKl;

                            if (rd <= pki && !nodesConnected(net.edges, node, net.nodes[j]) && !node.id.Equals(net.nodes[k].id))
                            {
                                ComplexNetEdge edge = new ComplexNetEdge();
                                edge.id = "edge" + i + "-" + j;
                                edge.directed = false;
                                edge.source = node;
                                edge.target = net.nodes[k];
                                node.edges.Add(edge);
                                net.nodes[k].edges.Add(edge);
                                net.edges.Add(edge);
                                break;
                            }
                        }
                    }
                }
            }

            return net;
        }

        public ComplexNet generateBAModelSimplifiedA(int N, int m0, int M)
        {
            ComplexNet net = new ComplexNet();
            if (M > 0 && M < m0 && m0 < N)
            {
                //tworzenie m0 wezlow
                for (int i = 0; i < m0; i++)
                {
                    ComplexNetNode node = new ComplexNetNode();
                    node.id = "node" + i;
                    net.nodes.Add(node);
                }

                //łączenie wierzcholkow kazdy z kazdym
                for (int i = 0; i < m0; i++)
                {
                    for (int j = i + 1; j < m0; j++)
                    {
                        ComplexNetEdge edge = new ComplexNetEdge();
                        edge.id = "edge" + i + j;
                        edge.directed = false;
                        edge.source = net.nodes[i];
                        edge.target = net.nodes[j];
                        net.nodes[i].edges.Add(edge);
                        net.nodes[j].edges.Add(edge);
                        net.edges.Add(edge);
                    }
                }

                Random random = new Random();
                for (int i = m0; i < N; i++)
                {
                    ComplexNetNode node = new ComplexNetNode();
                    node.id = "node" + i;
                    net.nodes.Add(node);

                    for (int j = 0; j < M; j++)
                    {
                        int r = random.Next(i);
                        while(nodesConnected(net.edges, node, net.nodes[r])) {
                            r = random.Next(i);
                        }

                        ComplexNetEdge edge = new ComplexNetEdge();
                        edge.id = "edge" + i + j;
                        edge.directed = false;
                        edge.source = node;
                        edge.target = net.nodes[r];
                        net.nodes[i].edges.Add(edge);
                        net.nodes[r].edges.Add(edge);
                        net.edges.Add(edge);
                    }
                }
            }

            return net;
        }

        public ComplexNet generateBAModelSimplifiedB(int N, int M)
        {
            ComplexNet net = new ComplexNet();

            for (int i = 0; i < N; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            Random random = new Random();
            for (int i = 0; i < M; i++)
            {
                int r = random.Next(N);
                ComplexNetNode source = net.nodes[r];
                
                double sumKj = 0;
                for (int j = 0; j < N; j++)
                {
                    sumKj += net.nodes[j].edges.Count + 1;
                }

                double rd = random.NextDouble();
                double p = 0;
                for (int j = 0; j < N; j++)
                {
                    p += (net.nodes[j].edges.Count + 1) / sumKj;
                    if (rd <= p && !nodesConnected(net.edges, source, net.nodes[j]) && r!=j)
                    {
                        ComplexNetEdge edge = new ComplexNetEdge();
                        edge.id = "edge" + i + "-" + j;
                        edge.directed = false;
                        edge.source = source;
                        edge.target = net.nodes[j];
                        net.nodes[r].edges.Add(edge);
                        net.nodes[j].edges.Add(edge);
                        net.edges.Add(edge);
                        break;
                    }
                }
            }

            return net;
        }

        public ComplexNet generateKleinbergModel(int n, int p, int q, int r)
        {
            ComplexNet net = new ComplexNet();

            //tworzenie siatki
            ComplexNetNode[,] lattice = new ComplexNetNode[n, n];

            //tworzenie wezlow
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    lattice[i, j] = new ComplexNetNode();
                    lattice[i, j].id = "node_" + i + "_" + j;
                    net.nodes.Add(lattice[i, j]);
                }
            }

            //tworzenie polaczen z sasiadami wg parametru p
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    for (int m = 0; m <= p; m++)
                    {
                        for (int k = i - m; k <= i + m; k++)
                        {
                            for (int l = j - m; l <= j + m; l++)
                            {
                                if ((l <= k + j - i + m) && (l >= -k + j + i - m) && (l <= -k + j + i + m) && (l >= k + j - i - m))
                                {
                                    if (k >= 0 && k < n && l >= 0 && l < n && !lattice[i, j].Equals(lattice[k, l]))
                                    {
                                        ComplexNetEdge edge = new ComplexNetEdge();
                                        edge.id = "edge" + i + j + "_" + k + l;
                                        edge.directed = true;
                                        edge.source = lattice[i, j];
                                        edge.target = lattice[k, l];
                                        lattice[i, j].edges.Add(edge);
                                        lattice[k, l].edges.Add(edge);
                                        net.edges.Add(edge);
                                    }
                                }
                            }
                        }
                    }
                }
            }

            //tworzenie losowych polaczen
            int qe = 0;
            Random random = new Random();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    double sum = 0;
                    for (int k = 0; k < n; k++)
                    {
                        for (int l = 0; l < n; l++)
                        {
                            sum += Math.Pow((Math.Abs(k - i) + Math.Abs(l - j)), -r);
                        }
                    }
                    double rand = random.NextDouble();
                    for (int k = 0; k < n; k++)
                    {
                        for (int l = 0; l < n; l++)
                        {
                            if (!lattice[i, j].Equals(lattice[k, l]))
                            {
                                double prob = Math.Pow((Math.Abs(k - i) + Math.Abs(l - j)), -r);// / sum;
                                if (prob >= rand)
                                {
                                    ComplexNetEdge edge = new ComplexNetEdge();
                                    edge.id = "edge" + i + j + "_" + k + l;
                                    edge.directed = true;
                                    edge.source = lattice[i, j];
                                    edge.target = lattice[k, l];
                                    lattice[i, j].edges.Add(edge);
                                    lattice[k, l].edges.Add(edge);
                                    net.edges.Add(edge);
                                    qe++;
                                    if (qe == q) return net;
                                }
                            }
                        }
                    }
                }
            }
            return net;
        }

        public ComplexNet generateAlfaModel(int n, double k, double alfa)
        {
            ComplexNet net = new ComplexNet();

            for (int i = 0; i < n; i++)
            {
                ComplexNetNode node = new ComplexNetNode();
                node.id = "node" + i;
                net.nodes.Add(node);
            }

            Random random = new Random();
            while (true)
            {
                double p = random.NextDouble() * Math.Pow(calculateNewtonSymbol(n, 2), -2);
                for (int i = 0; i < n; i++)
                {
                    double r = random.NextDouble();
                    double sumRij = 0;
                    double[,] R = new double[n,n];
                    for (int j = 0; j < n; j++)
                    {
                        R[i,j] = calculateRij(net.nodes[i], net.nodes[j], numOfVerticesAdjacentTo(net.nodes[i], net.nodes[j]), k, p, alfa);
                        sumRij += R[i,j];
                    }

                    double pij = 0;
                    for (int j = 0; j < n; j++)
                    {
                        if (i != j)
                        {
                            pij += R[i, j] / sumRij;
                            if (r <= pij)
                            {
                                ComplexNetEdge edge = new ComplexNetEdge();
                                edge.id = "edge" + i + "_" + j;
                                edge.directed = false;
                                edge.source = net.nodes[i];
                                edge.target = net.nodes[j];
                                net.nodes[i].edges.Add(edge);
                                net.nodes[j].edges.Add(edge);
                                net.edges.Add(edge);
                                if (calculateAverageGraphDegree(net) >= k) return net;
                                break;
                            }
                        }
                    }
                }

            }
            
            return net;
        }

        private int calculateAverageGraphDegree(ComplexNet net)
        {
            return 2*net.edges.Count/net.nodes.Count;
        }

        private int numOfVerticesAdjacentTo(ComplexNetNode node1, ComplexNetNode node2)
        {
            int n = 0;
            foreach (ComplexNetEdge edge in node1.edges)
            {
                if ( (node1.id.Equals(edge.source.id) && nodesConnected(node2.edges, node2, edge.target)) || (node1.id.Equals(edge.target.id) && nodesConnected(node2.edges, node2, edge.source)) )
                {
                    n++;
                }
            }
            return n;
        }

        private double calculateRij(ComplexNetNode nodei, ComplexNetNode nodej, int mij, double k, double p, double alfa)
        {
            if (nodei.id.Equals(nodej.id) || nodesConnected(nodei.edges, nodei, nodej)) return 0;
            if (mij >= k) return 1;
            if (mij == 0) return p;

            return Math.Pow(mij / k, alfa) * (1 - p) + p;
        }

        private int calculateNewtonSymbol(int n, int k)
        {
            int result = 1;
            for (int i = 1; i < k; i++)
            {
                result *= (n - i + 1) / i;
            }
            return result;
        }
    }
}
